package com.kobe.algorithm.leetcode.case5;

/**
 * @author ：caopengfei
 * @date ：2021/2/23
 *
 * {
 * P(i,i)=true
 * P(i,i+1)=(Si==Si+1)
 * ​	}
 * 动态规划解法
 * 填一个三角矩阵
 * P(i,j)=P(i+1,j−1)∧(Si ==Sj)
 */
public class Solution2 {

    public String longestPalindrome(String s) {
         int n = s.length();
         boolean [][] dp = new boolean[n][n];
         if(n<2){
             return s;
         }
         //当前最长的回文子串
         String ans = "";
         //l =  i和j相隔的位数
         for(int l = 0; l < n ; l++){
             for(int i = 0; i < n - l ;i++){
                 int j = i+l;
                 if(l == 0){
                     //对接线
                     dp[i][j] = true;
                 }else if (l == 1){
                     //ij 相邻
                     dp[i][j] = (s.charAt(i) == s.charAt(j));
                 }else{
                     dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]);
                 }
                 if(dp[i][j] && l+1 >ans.length()){
                     ans = s.substring(i,i+l+1);
                 }
             }

         }
         return ans;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        System.out.println(solution2.longestPalindrome("abb"));
    }
}
